public class Solution03 {
	// 双指针
	public boolean findTarget(TreeNode root, int k) {
		BSTIterator bst = new BSTIterator(root);
		BSTIteratorReversed bstr = new BSTIteratorReversed(root);

		int next = bst.next();
		int prev = bstr.prev();
		int sum = 0;
		while (next != prev) {
			sum = next + prev;
			if (sum == k) {
				return true;
			} else if (sum < k) {
				next = bst.next();
			} else {
				prev = bstr.prev();
			}
		}
		return false;
	}
}

/**
 * 中序遍历迭代器
 */
class BSTIterator {
	private TreeNode curNode;
	private Deque<TreeNode> stack;

	public BSTIterator(TreeNode root) {
		curNode = root;
		stack = new ArrayDeque<>();
	}

	public int next() {
		while (curNode != null) {
			stack.offerLast(curNode);
			curNode = curNode.left;
		}
		curNode = stack.pollLast();
		int val = curNode.val;
		curNode = curNode.right;
		return val;
	}

	public boolean hasNext() {
		return curNode != null || !stack.isEmpty();
	}
}

/**
 * 逆中序遍历迭代器
 */
class BSTIteratorReversed {
	private TreeNode curNode;
	private Deque<TreeNode> stack;

	public BSTIteratorReversed(TreeNode root) {
		curNode = root;
		stack = new ArrayDeque<>();
	}

	public boolean hasPrev() {
		return curNode != null || !stack.isEmpty();
	}

	public int prev() {
		while (curNode != null) {
			stack.offerLast(curNode);
			curNode = curNode.right;
		}
		curNode = stack.pollLast();
		int val = curNode.val;
		curNode = curNode.left;
		return val;
	}
}
